package algorithm.middle;


import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
 * 输入: arr = [1,2,3,4,5,6,7,8]
 * 输出: 5
 * 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
 * https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
 */
public class LenLongestFibSubseq873 {


    //动态规划
    public static int lenLongestFibSubseq(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int index = 0; index < arr.length; index++) {
            map.put(arr[index], index);
        }
        int res = 0;
        //序列至少3位
        //dp[j][i] j、i为序列最后两位。
        //arr[k]+arr[j]=arr[i] ==>arr[i] - arr[j] = arr[k]
        //如果arr[k]存在，则dp[j][i] = dp[k][j] + 1
        int[][] dp = new int[arr.length - 1][arr.length];
        for (int i = 0; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
                //因为数组单调递增，k如果存在必定在0～j下标之间
                int k = map.getOrDefault(arr[i] - arr[j], -1);
                if (k >= 0) {
                    //k存在
                    dp[j][i] = Math.max(dp[k][j] + 1, 3);
                }
                res = Math.max(res, dp[j][i]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        lenLongestFibSubseq(new int[]{1, 2, 3, 4, 5, 6, 7, 8});
    }
}
